package hotLeetcode;

import java.util.*;

public class H16Leetcode41 {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int min = 1;
        for (int num : nums) {
            if (num == min) {
                min++;
            }
        }

        return min;

    }

    //hash 法
    public int firstMissingPositive2(int[] nums) {
        int[] hash = new int[nums.length];


        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        int temp = 1;

        for (int i = 0; i < list.size(); i++) {
            if (list.contains(temp)) {
                temp++;
            }

        }
        return temp;

    }

    public int firstMissingPositive3(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) nums[i] = len + 1;
        }

        for (int i = 0; i < len; i++) {
            int num = Math.abs(nums[i]);
//            if (num <= len) nums[num - 1] *= -1;
            if (num <= len) nums[num - 1] = -Math.abs(nums[num - 1]);
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;

    }






    public static void main(String[] args) {
        H16Leetcode41 h16Leetcode41 = new H16Leetcode41();
        int[] nums = {1,1};

        System.out.println(h16Leetcode41.firstMissingPositive3(nums));
    }

}
